/**********************************************************************
**	Authors: Erik Sapir & Lior Zibi

**
** Optimistic List implementation: first find element in list,
** than lock and validate element still in list and are adjacent.
**
**
**********************************************************************/
 
#ifndef __OPTIMISTIC_LIST__H
#define __OPTIMISTIC_LIST__H

#include "framework/cpp_framework.h"
#include <memory>
#include "set.h"

using namespace CMDR;

template<typename T>
class OptimisticList : public set<T> {

private:

	//liat node
	class Node : public HazardMemory::Object {
	public:
		const T					m_item; //item stored in node
		VolatileType<Node*>	m_next; //next node in list
		CMDR::ReentrantLock			m_lock; // synchronized node
 
		Node(const T& item) : m_item(item), m_next(null) { }
		Node(const T& item, Node* const next) : m_item(item), m_next(next) { }

		virtual ~Node() {;}

		virtual bool isValid() { return true; }
		virtual HazardMemory::Object* getNextValid(const int indx) {
			return m_next;
		}
		virtual HazardMemory::Object* getNextValid(const int indx, int& flag) {
			flag = 0; 
			return m_next;
		}

		//lock node
		void Lock()  { m_lock.lock(); }

		//unlock node
		void UnLock() { m_lock.unlock(); }
	};

private:

	VolatileType<Node*>	m_head; //First list entry
	SnapshotCounter		m_counter; //counter for number of element in the list

public:

	OptimisticList(int numOfThreads) :  m_counter(numOfThreads) {
		printf("\n\tSet Is: Optimistic List\n");

		// Add sentinels to start and end
		m_head = new Node (Integer::MIN_VALUE, null);
		Node* tail = new Node(Integer::MAX_VALUE);
		m_head->m_next = tail;
	}

	//desctructor - removes all list elements
	~OptimisticList() {
		//we assume no one access the object at this point.
		Node* curr = m_head;
		Node* next = null;

		//go ovel all list elements and delete them
		while(null != curr) {
			next = curr->m_next;
			delete curr;

			curr = next;
		}
	}
		 
	bool add(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;
		int returnCode = 2;

		while (true) {
			pred = m_head;
			curr.extractNext(pred, 0);

			//search for first element equal or larger than new element
			
			while (curr->m_item < item) {	
				pred = curr;
				curr.extractNext(pred, 0);
			}

			//lock  both pred and curr
			pred->Lock();
			curr->Lock();

			try {
				//make sure pred and curr still in list and that pred.next = curr
				if (validate(pred, curr)) {
					if (curr->m_item == item) {
						//element already in list - nothing to add
						returnCode = 1;
					} else {
						// add new element to list
						std::auto_ptr<Node> node(new Node(item, curr.getReference()));
						pred->m_next = node.get();
						node.release();

						//element added successfully - increment number of elements in list
						m_counter.inc(threadID);
						returnCode = 0;
					}
				}		
			} catch (const std::exception& ) {
				returnCode = 1;
			}

			//unlock both pred and curr
			curr->UnLock();
			pred->UnLock();

			if (returnCode == 0)
				return true;
			else if (returnCode ==1)
				return false;
		}
	}

	bool remove(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;
		int returnCode = 2;

		while (true) {
			pred = m_head;
			curr.extractNext(pred, 0);

			//search for first element equal or larger than element to remove
			while (curr->m_item < item) {
				pred = curr;
				curr.extractNext(pred, 0);
			}

			//lock both pred and curr
			pred->Lock();
			curr->Lock();

			try {
				//make sure pred and curr still in list and that pred.next = curr
				if (validate(pred, curr)) {
					if (curr->m_item == item) {
						// remove element from list
						pred->m_next = curr->m_next;

						//retire node - will be acctually deleted when not used anymore
						curr.retire();

						//element removed successfully - decrement number of elements in list
						m_counter.dec(threadID);

						returnCode = 0;
					} else {
						// element not in list - nothing to remove
						returnCode = 1;	
					}
				}		
			} catch (const std::exception& ){
				returnCode = 1;
			}

			//unlock both pred and curr
			curr->UnLock();
			pred->UnLock();

			if (returnCode == 0){		
				return true;
			} else if (returnCode ==1){
				return false;		
			}
		} 
	}

	bool contains(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;

		int returnCode = 2;

		while (true) {
			pred = m_head;
			curr.extractNext(pred, 0);

			//search for first element equal or larger than element we are searching
			while (curr->m_item < item) {
				pred = curr;
				curr.extractNext(pred, 0);
			}

			//lock both pred and curr
			pred->Lock();
			curr->Lock();

			try {
				//make sure pred and curr still in list and that pred.next = curr
				if (validate(pred, curr)) {
					//return true iff element found in list
					if (curr->m_item == item) 
						returnCode = 0;
					else
						returnCode = 1;	
				}		
			} catch (const std::exception& ) {
				returnCode = 1;
			}

			//unlock both pred and curr
			curr->UnLock();
			pred->UnLock();

			if (0 == returnCode)
				return true;
			else if (1 == returnCode)
				return false; 			
		} 
	}

	void clean(int threadID) {
		HazardMemory::Ptr<Node> head;
		HazardMemory::Ptr<Node> curr;
		head = m_head;
		head->Lock();
		curr.extractNext(head, 0);

		//go over all elements in list and remove them.
		try {
			while(curr->m_item < Integer::MAX_VALUE) {
				curr->Lock();
				try {
					head->m_next = curr->m_next;

					//retire node - will be acctually deleted when not used anymore
					curr.retire();

					//element removed successfully - decrement number of elements in list
					m_counter.dec(threadID);

				} catch (const std::exception& ){}

				curr->UnLock();
				curr.extractNext(head, 0);
			}
		}
		catch (const std::exception& ){}
	}

	bool isEmpty(int threadID) {
		HazardMemory::Ptr<Node> head;
		HazardMemory::Ptr<Node> succ;
		bool returnValue;

		//lock head and head.next and check if nead.next in the tail of set
		head = m_head;
		head->Lock();
		try {
			succ.extractNext(head, 0);
			succ->Lock();
			try {
				//list is empty iff head pointing to tail
				returnValue = (succ->m_item == Integer::MAX_VALUE);
			}
			catch (const std::exception& ){}
			succ->UnLock();
		} catch (const std::exception& ){}
 		head->UnLock();
		return returnValue;
	}
	int size(int threadID){
		return m_counter.scan();
	}

private:

	/*
	 * Check that prev and curr are still in list and adjacent
     */
	bool validate(HazardMemory::Ptr<Node>& pred, HazardMemory::Ptr<Node>& curr) {
		HazardMemory::Ptr<Node> entry;
		HazardMemory::Ptr<Node> nextEntry;

		entry = m_head;
		while (entry->m_item <= pred->m_item) {
			if (entry == pred)
				//make sure pred and curr and adjacent
				return (pred->m_next == curr.getReference());

			nextEntry.extractNext(entry, 0);
			entry = nextEntry;
		}

		return false;
	}
}; 

#endif // __FINE_LIST__H
